#include <iostream>
#include <vector>
#include <deque> // 双端队列

// 暴力求解 超时
std::vector<int> maxSlidingWindow(std::vector<int>& nums, int k) {
    std::vector<int> result;
    for (int i{}, len = nums.size() - k + 1; i < len; i++) {
        int num = nums[i];
        for (int j{ 1 }; j < k; j++) {
            int idx = j + i;
            if (nums[idx] > num) {
                num = nums[idx];
            }
        }
        result.push_back(num);
    }

    return result;
}

// 单调队列 保持队列单调递增
class MyQueue {
private:
    std::deque<int> theQueue;
public:
    void push(int x) {
        while (!theQueue.empty() && x > theQueue.back()) {
            theQueue.pop_back();
        }
        theQueue.push_back(x);
    }
    // 弹出的数值和单调队列首元素相同是才需要弹出
    void pop(int x) {
        if (!theQueue.empty() && x == theQueue.front()) {
            theQueue.pop_front();
        }
    }
    int front() {
        return theQueue.front();
    }
};

std::vector<int> maxSlidingWindow2(std::vector<int>& nums, int k) {
    MyQueue que;
    std::vector<int> result;
    // 前k个元素入队列
    for (int i{}; i < k; i++) {
        que.push(nums[i]);
    }
    
    for (int i = k; i < nums.size(); i++) {
        result.push_back(que.front()); // 记录最大元素
        que.pop(nums[i - k]); // 滑动窗口第一个元素弹出
        que.push(nums[i]);
    }

    result.push_back(que.front());

    return result;
}


void printVector(std::vector<int>& nums) {
    for (int i{}, len = nums.size(); i < len; i++) {
        std::cout << "[" << i << "] = " << nums[i] << "\n";
    }
}

int main() {
    std::vector<int> nums{ 1,3,-1,-3,5,3,6,7 };
    std::vector<int> result = maxSlidingWindow(nums, 3);
    printVector(result);

    std::cout << "==========================\n";

    result = maxSlidingWindow2(nums, 3);
    printVector(result);
}